/** The Traveling Sales Person problem solution class
 * This program includes four TSP solution methods
 * @author Arnas Kainskas and modified by Softhut Group
 * @author i5arka@vaidila.vdu.lt
 * @version 2.0 
 */

package uns.fit.gis.alg;

public class Tsp {

	//** public sector

	/** Array of current route */
	public int route[];

	//** private sector

	/** best=0 , worse=1 */
	private int best_or_worst_route_calculation;

	private int cities; // current cities number
	private int iterations; // number of iterations
	private int[][] d; // distances matrix
	private boolean[] visitedCities; // city is visited or not 

	/**  Constructs a TSP using users parameters. 
	 @param d distance matrix
	 @param best_or_worse   best_route = 0;  worse_route = 1;
	 **/
	public Tsp(int[][] d, int best_or_worst) {
		cities = d.length;
		route = new int[cities + 1];
		this.d = d;
		visitedCities = new boolean[d.length]; // city is visited or not 
		iterations = 0;
		this.best_or_worst_route_calculation= best_or_worst;
	}

	//***   

	//** public methods sector

	/** Returns current iterations number 
	 * @return Returns number of iterations, needed to calculate TSP distance and route
	 */
	public int getIterationsNumber() {
		return iterations;
	}

	/** Calculates the traveling sales person distance using Nearest Neighbour calculation method
	 * @return Returns TSP distance.
	 */
	public double nearestNeighbour() {
		initCalc();
		return nearest_n(0);
	}

	/** Calculates the traveling sales person distance using Repeatetive Nearest Neighbour calculation method
	 * @return Returns TSP distance.
	 */
	public double repeatetiveNearestNeighbour() {

		double min_dist = Double.MAX_VALUE;
		double nn_dist;
		int rep_route[] = new int[cities + 1]; // a copy of route used for rnn method    	

		initCalc();
		for (int i = 0; i < cities; i++) {
			// clear visited cities values
			for (int k = 0; k < cities; k++)
				visitedCities[k] = false;

			// get the distance and route starting from the city i	
			nn_dist = nearest_n(i);
			if (nn_dist < min_dist) {
				min_dist = nn_dist;
				for (int j = 0; j < cities + 1; j++)
					rep_route[j] = route[j];
			}
		}
		for (int j = 0; j < cities + 1; j++)
			route[j] = rep_route[j];

		return min_dist;
	}

	/** Calculates the traveling sales person distance using Random Two Optimals Exchange calculation method 
	 * @return Returns TSP distance.
	 */
	public double randomTwoOptimals() {
		initCalc();
		return two_optimals(1);
	}

	/** Calculates the traveling sales person distance using Nearest Neighbour initial value Two Optimals Exchange calculation 
	 * @return Returns TSP distance.
	 */
	public double nnTwoOptimals() {
		initCalc();
		return two_optimals(0);
	}

	// two optimals exchange algorythm
	private double two_optimals(int which) {

		int[] ptr = new int[cities];
		int ahead, i1, i2, index, j1, j2, last, limit, n1, n2, next, s1 = 0, s2 = 0, t1 = 0, t2 = 0;

		double max, max1, tweight = 0;
		int n = cities;
		if (which == 0) {
			tweight = nearest_n(0);
		} else {
			for (int i = 0; i < n; i++) {
				route[i] = i;
				iterations++;
				if (i != n - 1) {
					tweight = tweight + d[i + 1][i];
				}
			}
			route[n] = 0;
			tweight = tweight + d[0][n - 1];
			iterations++;
		}

		n1 = n - 1;
		n2 = n1 - 1;

		// ptr yra masyvas, kuris parodo i kuri miesta vaziuoja sekanciame zingsnyje   
		for (int i = 0; i < n1; i++)
			ptr[route[i]] = route[i + 1];
		ptr[route[n1]] = route[0];

		//lygina visas ne galimas poras (poros negali tureti bendru virsuniu)
		do {
			max = 0;
			i1 = 0;
			for (int i = 0; i < n2; i++) {
				limit = (i == 0) ? n1 : n;
				i2 = ptr[i1];
				j1 = ptr[i2];
				for (int j = i + 2; j < limit; j++) {
					iterations++;
					j2 = ptr[j1];
					max1 = d[i1][i2] + d[j1][j2] - (d[i1][j1] + d[i2][j2]);

					// Jei surasta pora, kurios virsunes sukeitus vietomis
					// gaunamas trumpesnis atstumas, tai virsunes reikia isaugoti

					if (max1 > max) {
						s1 = i1;
						s2 = i2;
						t1 = j1;
						t2 = j2;
						max = max1;
					}
					j1 = j2;
				}
				i1 = i2;
			}

			// Jei turime geresni marsruta , reikia pakeisti informacija.
			if (max > 0) {

				//  Sukeicia virsunes
				ptr[s1] = t1;
				next = s2;
				last = t2;

				do {
					ahead = ptr[next];
					ptr[next] = last;
					last = next;
					next = ahead;
				} while (next != t2);
				//  Sumazina marsruto ilgi
				tweight = tweight - max;
			}
		} while (max != 0);

		// Pakeicia marsruta.
		index = 0;
		for (int i = 0; i < n; i++) {
			route[i] = index;
			index = ptr[index];
		}
		return tweight;
	}

	// nearest neighbour method      
	private double nearest_n(int start) {

		int next_c = 0, i, n;
		double mindist, distance = 0;
		i = start;
		for (n = 0; n < cities; n++) {
			mindist = Double.MAX_VALUE; // let it be, primary minimal distance
			for (int j = 0; j < cities; j++) {
				iterations++;
				if (n != cities - 1) { // to the start city we return in the last step
					if ((mindist > d[i][j]) && (i != j) && (visitedCities[j] != true)
									&& (j != start)) {
						mindist = d[i][j];
						next_c = j;
					}
				} else {
					mindist = d[i][start];
					next_c = start;
				}
			}

			visitedCities[i] = true;
			distance = distance + mindist;
			route[n] = i; // add visited city to a route array
			i = next_c; // city to which we go
		}

		// return to the start city
		visitedCities[i] = true;
		route[n] = i;
		return distance;
	}

	// init the matrix of distances values      
	private void initDistances() {
//		Initializing distance matrix for best route calculation
		if (best_or_worst_route_calculation == 0) {
			for (int i = 0; i < cities; i++) {
				visitedCities[i] = false; // at the begining all cities are not visited
				iterations = 0; // at the beginning number of iterationss is zero
			}
		} else {
			//Initializing distance matrix for worst route calculation

			for (int i = 0; i < cities; i++) {
				visitedCities[i] = false; // at the begining all cities are not visited
				iterations = 0; // at the beginning number of iterationss is zero
			}
		}
	}

	// method used to initialize calculations 
	private void initCalc() {
		initDistances();
	}

} ///~
